package dfs_bfs;
/**
 * dfs ---- used需要设置三个状态，0-未访问，1-能够学完， 2-代表循环
 * bfs ---- 使用队列
 */

import java.util.*;

public class lc207 {
    public static void main(String[] args) {
        System.out.println(canFinish(2, new int[][]{{0,1}}));
    }
    public static boolean canFinish_dfs(int numCourses, int[][] prerequisites) {
        int[] used = new int[numCourses];
        List<List<Integer>> cou = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            cou.add(new ArrayList<>());
        }
        for (int j = 0; j < prerequisites.length; j++) {
                cou.get(prerequisites[j][0]).add(prerequisites[j][1]);
            }
        for (int i = 0; i < numCourses; i++) {
            if(!dfs(i, used, cou))
                return false;
        }
        return true;
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] count = new int[numCourses];
        List<List<Integer>> cou = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            cou.add(new ArrayList<>());
        }
        for (int j = 0; j < prerequisites.length; j++) {
            cou.get(prerequisites[j][1]).add(prerequisites[j][0]);
            count[prerequisites[j][0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if(count[i] == 0)
                queue.add(i);
        }
        while( !queue.isEmpty()){
            int t = queue.poll();
            numCourses--;
            for (int p : cou.get(t)) {
                count[p]--;
                if(count[p] == 0)
                    queue.add(p);
            }
        }
        return numCourses == 0;
    }
    public static boolean dfs(int i, int[] used, List<List<Integer>> cou){
        List<Integer> list = cou.get(i);
        if(list == null || list.size() == 0)
            return true;
        if(used[i] == 2)
            return false;
        if(used[i] == 1)
            return true;
        used[i] = 2;
        for (int j = 0; j < list.size(); j++) {
            if( !dfs(list.get(j), used, cou))
                return false;
        }
        used[i] = 1;
        return true;
    }
}
